package leetcode_jz_offer.day22_weiyunsuan;

/**
 * @author 美女
 * @date 2022/07/31 14:25
 **/

/**
 * 分析：一个数字只出现一次之外，其他数字都出现了三次，那么这些出现了三次的数字对应的二进制位上的数字和余上3==0
 *      统计所有数字的各二进制位中1的出现次数，并对3求余，结果则为只出现一次的数字。
 */

/**
 * 算法：
 * 1）将nums中所有数字展开为32位的二进制数，对所有数字的对应位的二进制进行计数（将对应的二进制位相加）
 * 1110+
 * 1110+
 * 1110+
 * 1001（对应二进制位计数相加）：
 * 4331
 * 2）对于相加后的结果的对应位：如果找到一个位的位数不能被3整除，说明这个位的数是构成目标数的一部分
 * 3）记录结果的当前二进制位代表的十进制位tmp,结果：循环res+=tmp得到结果
 * tmp=1;(2^0=1)res=0;
 * 1%3=1,res+=tmp=1;temp*=2=2(更新temp到下一个二进制位(每次都需要更新))
 * 3%3=0,不执行res+=temp;(temp*=2)=4
 * 3%3=0,不执行res+=temp;(temp*=2)=8
 * 4%3=1;res+=temp=1+8=9;(temp*=2)=16
 * 再前面位数全是0，0%3=0;res不执行，最后返回res就是只出现一个的数字
 */
public class Num56_II数组中数字出现的次数 {
    public int singleNumber(int[] nums) {
        //nums中所有数字展开成对应二进制，他们对应位的和存储到一个32长度数组中
        int[] byteArray=new int[32];
        for (int num:nums){//遍历每个数字
            for (int i = 0; i < 32; i++) {//每个数字对应的32位
                byteArray[i]+=((num>>i)&1)==1?1:0;//与1相与等于本身(1&0=0,1&1=1)
            }
        }
        //相加后结果对应位byteArray[i]可否被3整除,如果找到一个位的位数不能被3整除，说明这个位的数是构成目标数的一部分,将对应位转化为十进制形式
        //转化方法：temp记录每个位对应的十进制数：2^0;2^1;2^2;2^3...,当不能整除（余数为1）时，res+=temp。最后返回res即可
        int res=0;
        int temp=1;
        for (int i = 0; i < 32; i++) {
            if(byteArray[i]%3==1){
                res+=temp;
            }
            temp*=2;
        }
        return res;
    }
}
